package com.leetcode;

import java.util.ArrayList;

public class PathSum {
	public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return sum == root.val;
		return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
	
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList res = new ArrayList();
        ArrayList<Integer> cur = new ArrayList<Integer>();
        traverse(res, cur, root, sum);
        return res;
    }
	
	private void traverse(ArrayList res, ArrayList<Integer> cur, TreeNode node, int sum) {
		if (node == null) return;
		if (node.left == null && node.right == null) {
			if (sum == node.val) {
				ArrayList<Integer> t = new ArrayList<Integer>(cur);
				t.add(node.val);
				res.add(t);
			}
			return;
		}
		
		cur.add(node.val);
		traverse(res, cur, node.left, sum - node.val);
		traverse(res, cur, node.right, sum - node.val);
		cur.remove(cur.size()-1);
	}
	
	private class TreeNode {
		TreeNode left;
		TreeNode right;
		int val;
		public TreeNode(int val) {
			this.val = val;
		}
	}
}
